package com.lijing.BackTracing2;

import sun.util.locale.provider.FallbackLocaleProviderAdapter;

import java.util.*;

/**
 * @Description 给定⼀个数组 candidates 和⼀个⽬标数 target ，找出 candidates 中所有可以使数字和为 target 的组合
 * candidates 中的每个数字在每个组合中只能使⽤⼀次。
 * 说明：
 * 所有数字（包括⽬标数）都是正整数。
 * 解集不能包含重复的组合。
 * @title: Combination5
 * @Author LiJing
 * @Date: 2021/4/57:42 下午
 * @Version 1.0
 */
public class Combination5 {
    static List<LinkedList<Integer>> result = new ArrayList<>();
    static LinkedList<Integer> path = new LinkedList<>();
    static int sum;

    public static void main(String[] args) {
        int[] candidates = {2,5,2,1,2};
        int target = 5;
        boolean[] used = new boolean[candidates.length];
        System.out.println(Arrays.toString(used));
        Arrays.sort(candidates);
        System.out.println(Arrays.toString(candidates));
        backTracing(0,candidates,target,used);
        System.out.println(result);
    }

    /**
     * 回溯
     * @param startIndex 开始index
     * @param candidates candidates
     * @param target target
     * @param used 用于标志是树枝去重还是树层去重，如果candidates[i] == candidates[i-1] && used[i-1]==false，说明在同一树层
     *             需要去重，如果used[i-1]==true，说明在同一树枝，不需要去重
     */
    public static void backTracing(int startIndex, int[] candidates, int target, boolean[] used){
        if (sum == target){
            result.add(new LinkedList<>(path));
            return;
        }

        for (int i = startIndex; i < candidates.length && sum + candidates[i] <= target; i++) {
            //处理当前节点
            if (i>0 && candidates[i] == candidates[i-1] && !used[i - 1]){
                continue;
            }
            sum += candidates[i];
            path.addLast(candidates[i]);
            used[i] = true;
            //递归
            backTracing(i+1,candidates,target,used);
            //回溯
            used[i] = false;
            sum -= candidates[i];
            path.removeLast();
        }
    }

    /**
     * 清洗数组中重复的数字
     * @param arr 待清洗的数组
     */
    public static void washArray(int[] arr){

    }

}
